package com.bo.day20231201;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * 堆：优先级队列
 * 堆可以理解成一个完全二叉树
 * 完全二叉树:叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
 * 比如：
 * 完全二叉树
 * 9
 * / \
 * 7   8
 * /
 * 5
 * 不是完全二叉树
 * 9
 * / \
 * 7  8
 * \
 * 5
 * 完全二叉树位置公式
 * i的父节点=(i-1)/2
 * i的左节点=i*2+1
 * i的右节点=i*2+2
 * 比如大根堆
 * 9
 * /  \
 * 5    8
 * / \  / \
 * 2  3 6  7
 * <p>
 * arr[9,5,8,2,3,6,7]
 *
 * @Author: gpb
 * @Date: 2023/12/4 16:44
 * @Description:
 */
public class Heap {


    public static void main (String[] args) {
        MaxHeap maxHeap = new MaxHeap(5);
        maxHeap.push(5);
        maxHeap.push(9);
        maxHeap.push(2);
        maxHeap.push(9);
        maxHeap.push(7);
        System.out.println(maxHeap.pop());
        System.out.println(maxHeap.pop());
        System.out.println(maxHeap.pop());
        System.out.println(maxHeap.pop());
        System.out.println(maxHeap.pop());
        System.out.println("小根堆");
        SmallHeap smallHeap = new SmallHeap(5);
        smallHeap.push(5);
        smallHeap.push(9);
        smallHeap.push(2);
        smallHeap.push(9);
        smallHeap.push(7);
        System.out.println(smallHeap.pop());
        System.out.println(smallHeap.pop());
        System.out.println(smallHeap.pop());
        System.out.println(smallHeap.pop());
        System.out.println(smallHeap.pop());

        System.out.println("系统api堆");
        // 小根堆
        PriorityQueue<Integer> heap = new PriorityQueue<>(new MyComparator());
        heap.add(5);
        heap.add(5);
        heap.add(5);
        heap.add(3);
        // 5 , 3
        System.out.println(heap.peek());
        heap.add(7);
        heap.add(0);
        heap.add(7);
        heap.add(0);
        heap.add(7);
        heap.add(0);
        System.out.println(heap.peek());
        while (!heap.isEmpty()) {
            System.out.println(heap.poll());
        }
        int max = 0;
        for (Map.Entry<Object, Object> m : new HashMap<>().entrySet()) {
            Object value = m.getValue();
        }

        System.out.println("开始测试。。。");
        int value = 1000;
        int limit = 100;
        int testTimes = 1000000;
        for (int i = 0; i < testTimes; i++) {
            int curLimit = (int) (Math.random() * limit) + 1;
            MaxHeap my = new MaxHeap(curLimit);
            RightMaxHeap test = new RightMaxHeap(curLimit);
            int curOpTimes = (int) (Math.random() * limit);
            for (int j = 0; j < curOpTimes; j++) {
                if (my.isEmpty() != test.isEmpty()) {
                    System.out.println("Oops!");
                }
                if (my.isFull() != test.isFull()) {
                    System.out.println("Oops!");
                }
                if (my.isEmpty()) {
                    int curValue = (int) (Math.random() * value);
                    my.push(curValue);
                    test.push(curValue);
                } else if (my.isFull()) {
                    if (my.pop() != test.pop()) {
                        System.out.println("Oops!");
                    }
                } else {
                    if (Math.random() < 0.5) {
                        int curValue = (int) (Math.random() * value);
                        my.push(curValue);
                        test.push(curValue);
                    } else {
                        if (my.pop() != test.pop()) {
                            System.out.println("Oops!");
                        }
                    }
                }
            }
        }
        System.out.println("finish!");
    }

    /**
     * 大根堆
     */
    public static class MaxHeap {
        private int heapSize = 0;
        private final int limit;
        private int[] heap;

        public MaxHeap (int limit) {
            this.heap = new int[limit];
            this.limit = limit;
        }

        public boolean isEmpty () {
            return heapSize == 0;
        }

        public boolean isFull () {
            return heapSize == limit;
        }

        public void push (int value) {
            if (isFull()) {
                throw new RuntimeException("heap is full");
            }
            heap[heapSize] = value;
            //  heapInsert(heap, heapSize++);
            heapInsertRecursion(heap, heapSize++);
        }

        /**
         * 添加逻辑
         * 添加到数组最后一位,依次和父节点进行比较,如果比父节点大,和父节点交换
         *
         * @param heap  堆
         * @param index
         */
        private void heapInsert (int[] heap, int index) {
            while (heap[index] > heap[(index - 1) / 2]) {
                swap(heap, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        private void heapInsertRecursion (int[] heap, int index) {
            if (heap[index] < heap[(index - 1) / 2] || index == 0) {
                return;
            }
            swap(heap, index, (index - 1) / 2);
            index = (index - 1) / 2;
            heapInsertRecursion(heap, index);
        }

        public int pop () {
            int t = heap[0];
            swap(heap, 0, --heapSize);
            //heapify(heap, 0, heapSize);
            heapifyRecursion(heap, 0, heapSize);
            return t;
        }

        // 从index位置，往下看，不断的下沉
        // 停：较大的孩子都不再比index位置的数大；已经没孩子了
        private void heapify (int[] heap, int index, int heapSize) {
            // 左孩子
            int left = index * 2 + 1;
            // 如果有左孩子,有没有右孩子,有可能有没有
            while (left < heapSize) {
                // 找出最大孩子的下标,看看左孩子还是右孩子多大
                // 如果 left+1 小于 heapSize 说明存在右孩子,存在就比较左孩子还是右孩子多大
                int ans = (left + 1) < heapSize && heap[left + 1] > heap[left] ? left + 1 : left;
                // 当前位置和最大孩子进行比较,如果小于最大孩子,就继续下沉,如果大于就结束
                ans = heap[index] < heap[ans] ? ans : index;
                if (ans == index) {
                    break;
                }
                swap(heap, ans, index);
                index = ans;
                left = index * 2 + 1;
            }
        }

        // 从index位置，往下看，不断的下沉
        // 停：较大的孩子都不再比index位置的数大；已经没孩子了
        private void heapifyRecursion (int[] heap, int index, int heapSize) {
            // 左孩子
            int left = index * 2 + 1;
            if (left >= heapSize) {
                return;
            }
            // 找出最大孩子的下标,看看左孩子还是右孩子多大
            // 如果 left+1 小于 heapSize 说明存在右孩子,存在就比较左孩子还是右孩子多大
            int ans = (left + 1) < heapSize && heap[left + 1] > heap[left] ? left + 1 : left;
            // 当前位置和最大孩子进行比较,如果小于最大孩子,就继续下沉,如果大于就结束
            ans = heap[index] < heap[ans] ? ans : index;
            if (ans == index) {
                return;
            }
            swap(heap, ans, index);
            index = ans;
            heapifyRecursion(heap, index, heapSize);
        }

        /**
         * 数组位置交换
         */
        public static void swap (int[] arr, int l, int r) {
            int t = arr[l];
            arr[l] = arr[r];
            arr[r] = t;
        }
    }

    /**
     * 小根堆
     */
    public static class SmallHeap {
        private int heapSize = 0;
        private final int limit;
        private int[] heap;

        public SmallHeap (int limit) {
            this.heap = new int[limit];
            this.limit = limit;
        }

        public boolean isEmpty () {
            return heapSize == 0;
        }

        public boolean isFull () {
            return heapSize == limit;
        }

        public void push (int value) {
            if (isFull()) {
                throw new RuntimeException("heap is full");
            }
            heap[heapSize] = value;
           // heapInsert(heap, heapSize++);
            heapInsertRecursion(heap, heapSize++);
        }

        /**
         * 添加逻辑
         * 添加到数组最后一位,依次和父节点进行比较,如果比父节点大,和父节点交换
         *
         * @param heap  堆
         * @param index
         */
        private void heapInsert (int[] heap, int index) {
            while (heap[index] < heap[(index - 1) / 2]) {
                swap(heap, index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        private void heapInsertRecursion (int[] heap, int index) {
            if (heap[index] > heap[(index - 1) / 2] || index == 0) {
                return;
            }
            swap(heap, index, (index - 1) / 2);
            index = (index - 1) / 2;
            heapInsertRecursion(heap, index);
        }

        public int pop () {
            int t = heap[0];
            swap(heap, 0, --heapSize);
            //heapify(heap, 0, heapSize);
            heapifyRecursion(heap, 0, heapSize);
            return t;
        }

        // 从index位置，往下看，不断的下沉
        // 停：较大的孩子都不再比index位置的数大；已经没孩子了
        private void heapify (int[] heap, int index, int heapSize) {
            // 左孩子
            int left = index * 2 + 1;
            // 如果有左孩子,有没有右孩子,有可能有没有
            while (left < heapSize) {
                // 找出最小孩子的下标,看看左孩子还是右孩子小
                // 如果 left+1 小于 heapSize 说明存在右孩子,存在就比较左孩子还是右孩子小
                int ans = (left + 1) < heapSize && heap[left + 1] < heap[left] ? left + 1 : left;
                // 如果当前位置小于最小孩子,说明不需要下沉了,大于最小孩子,继续下沉
                ans = heap[index] < heap[ans] ? index : ans;
                if (ans == index) {
                    break;
                }
                swap(heap, ans, index);
                index = ans;
                left = index * 2 + 1;
            }
        }

        // 从index位置，往下看，不断的下沉
        // 停：较大的孩子都不再比index位置的数大；已经没孩子了
        private void heapifyRecursion (int[] heap, int index, int heapSize) {
            // 左孩子
            int left = index * 2 + 1;
            if (left >= heapSize) {
                return;
            }
            // 找出最小孩子的下标,看看左孩子还是右孩子小
            // 如果 left+1 小于 heapSize 说明存在右孩子,存在就比较左孩子还是右孩子小
            int ans = (left + 1) < heapSize && heap[left + 1] < heap[left] ? left + 1 : left;
            // 如果当前位置小于最小孩子,说明不需要下沉了,大于最小孩子,继续下沉
            ans = heap[index] < heap[ans] ? index : ans;
            if (ans == index) {
                return;
            }
            swap(heap, ans, index);
            index = ans;
            heapifyRecursion(heap, index, heapSize);
        }

        /**
         * 数组位置交换
         */
        public static void swap (int[] arr, int l, int r) {
            int t = arr[l];
            arr[l] = arr[r];
            arr[r] = t;
        }
    }

    public static class MyComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }

    }

    public static class RightMaxHeap {
        private int[] arr;
        private final int limit;
        private int size;

        public RightMaxHeap(int limit) {
            arr = new int[limit];
            this.limit = limit;
            size = 0;
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public boolean isFull() {
            return size == limit;
        }

        public void push(int value) {
            if (size == limit) {
                throw new RuntimeException("heap is full");
            }
            arr[size++] = value;
        }

        public int pop() {
            int maxIndex = 0;
            for (int i = 1; i < size; i++) {
                if (arr[i] > arr[maxIndex]) {
                    maxIndex = i;
                }
            }
            int ans = arr[maxIndex];
            arr[maxIndex] = arr[--size];
            return ans;
        }

    }
}
